class Solution(object):
    def largest1BorderedSquare(self, grid):
        m = len(grid)
        n = len(grid[0])
        h_grid = [[0 for _ in range(n)] for _ in range(m)]
        v_grid = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n - 1, -1, -1):
                if grid[i][j]:
                    if j == n - 1:
                        h_grid[i][j] = 1
                    else:
                        h_grid[i][j] = h_grid[i][j + 1] + 1
        for j in range(n):
            for i in range(m - 1, -1, -1):
                if grid[i][j]:
                    if i == m - 1:
                        v_grid[i][j] = 1
                    else:
                        v_grid[i][j] = v_grid[i + 1][j] + 1
        max_val = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    max_k = min(h_grid[i][j], v_grid[i][j])
                    for k in range(max_k, 0, -1):
                        if v_grid[i][j + k - 1] >= k and h_grid[i + k - 1][j] >= k:
                            max_val = max(max_val, k ** 2)
                            break
        return max_val


data = Solution()
# grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
# print(data.largest1BorderedSquare(grid))
grid = [[0, 0, 0, 1]]
print(data.largest1BorderedSquare(grid))
